#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @Author  : 邢建辉
# @Email   : xjh_0125@sina.com
# @Time    : 2022/1/10 15:33
# @Software: PyCharm
# @File    : l57_insert_range.py
from typing import List


class Solution:
    def insert_1(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        def overlap(a, b):
            return (a[0] >= b[0] and a[0] <= b[1]) or (a[0] <= b[0] and b[0] <= a[1]) or (a[0] >= b[0] and a[1] <= b[1])

        res = []
        inserted = False
        prev = newInterval
        if len(intervals) == 0:
            return [newInterval]
        for (idx, tp) in enumerate(intervals):
            if inserted:
                if prev[1] >= tp[0]:
                    if prev[1] < tp[1]:
                        prev[1] = tp[1]
                        res.append(prev)
                        res.extend(intervals[idx + 1:])
                        return res
                else:
                    res.append(prev)
                    res.extend(intervals[idx:])
                    return res
            else:
                if overlap(tp, newInterval):
                    inserted = True
                    prev = [min(tp[0], newInterval[0]), max(tp[1], newInterval[1])]
                else:
                    res.append(tp)
        # 此时就剩余prev未处理
        if inserted:
            last = intervals[-1]
            res.append([min(prev[0], last[0]), max(prev[1], last[1])])
        else:
            for (idx, tp) in enumerate(res):
                if tp[0] > prev[0]:
                    res.insert(idx, prev)
                    inserted = True
                    break
            if not inserted:
                res.append(prev)

        return res

    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        i, count = 0, len(intervals)
        while i < count and intervals[i][1] < newInterval[0]:
            res.append(intervals[i])
            i += 1
        while i < count and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        res.append(newInterval)
        while i < count:
            res.append(intervals[i])
            i += 1
        return res


if __name__ == '__main__':
    s = Solution()
    intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]]
    newInterval = [4, 8]
    # intervals = [[1, 3], [6, 9]]
    # newInterval = [2, 5]
    # intervals = []
    # newInterval = [5, 7]
    # intervals = [[1, 5]]
    # newInterval = [2, 7]
    # intervals = [[1, 5]]
    # newInterval = [5, 7]
    # intervals = [[1, 5]]
    # newInterval = [0, 0]
    intervals = [[3, 5], [12, 15]]
    newInterval = [0, 0]
    intervals = [[1, 3], [6, 9]]
    newInterval = [2, 5]
    print(s.insert(intervals, newInterval))
